Given an undirected graph $G = (V, E)$, with $|V| = n, |E| = m$, consider the following method of generating an independent set. Given a permutation $\sigma$ of the vertices, define a subset $S(\sigma)$ of the vertices as follows: for each vertex $i, i \in S(\sigma)$ if and only if no neighbor $j$ of $i$ precedes $i$ in the permutation $\sigma$.
\begin{itemize}
\item[(a)] Show that each $S(\sigma)$ is an independent set in $G$.
\item[(b)] Design a randomized algorithm to produce $\sigma$ with $|S(\sigma)| = \sum_{i=1}^n \frac{1}{d_i+1}$ where $d_i$ is the degree of vertex $i$.
\item[(c)] Prove that $G$ has an independent set of size at least $\sum_{i=1}^n \frac{1}{d_i+1}$.
\end{itemize}

\textbf{(a)} We will prove this by induction on the size of $S(\sigma)$.

\subparagraph*{For $|S(\sigma)| = 1$.} This is clearly true.

\subparagraph*{For $|S(\sigma)| = k$.} Assume it is true.

\subparagraph*{For $|S(\sigma)| = k+1$.} In order to add a new vertex $i$ in the $S(\sigma)$ we may skip several vertices from $\sigma$ in order to adhere to the ``neighbor'' rule. When we add $i$, we know that no neighbor of $i$ ($j$) belongs to the $S(\sigma)$. Additionally, $i$ is the last inserted vertex therefore does not have anything on its right. Consequently, the addition of $i$ did not change the fact that $S(\sigma)$ is an independent set.
\\\\
\textbf{(b)} We use the following randomized algorithm.

\begin{figure}[h]
\lstset{language=C, tabsize=2, frame=none, numbers=left, basicstyle=\small}
	\begin{lstlisting}[language=C]
	T : calculate the target size;
	do {
		PERM : create a random permutation of the vertices;
		empty S(sigma);
		while (PERM is not empty) {
			V = get_next(PERM);
			if (V does not have a neighbor in S(sigma)) {
				append(V, S(sigma));
			}
		}
	} while (|S(sigma)| != T); /*according to the question we need an independent set of size exactly T*/
	\end{lstlisting}
\end{figure}
This algorithm will repeatedly create a permutation $\sigma$ and calculate the $S(\sigma)$ for it until we get the wanted size. In question (c) we prove that a permutation with the wanted size always exists.

\textbf{(c)} We will use a random variable $X_v$ define as following:
\[
X_v = \left\{
\begin{array}{ll}
1 & \text{if $v$ $\in$ $S(\sigma)$}\\
0 & \text{otherwise}
\end{array}
\right.
\]

In order $v$ to appear in $S(\sigma)$, all its $d_v$ neighbors should succeed it in permutation $\sigma$. Therefore,
\[
E[X_v] = Pr[X_v = 1] = Pr[v \in S(\sigma)] = \dfrac{1}{d_v + 1}
\]
because $v$ has $d_v$ neighbors. Accordingly, the expected value of the size of $S(\sigma)$ is:
\[
E[|S(\sigma)|] = E[\sum \limits _{v \in V} X_v] = \sum \limits _{v \in V}E[X_v] = \sum \limits _{v \in V}\dfrac{1}{d_v + 1}
\]
Therefore, for every graph there is a permutation $\sigma$ with constructed $S(\sigma)$ of size $|S(\sigma)| \ge \sum _{v \in V}\frac{1}{d_v + 1}$, since there is a positive probability that the size of $S(\sigma)$ is greater/equal than its expectation. Since in question (a) we proved that $S(\sigma)$ is a independent set, we showed the wanted result.